#include <cstdio>
#include <cstring>
#define INF 100000
#define MAXN 20

int n;
int edge[MAXN][MAXN];
int s[MAXN];
int dist[MAXN];
int path[MAXN];

void dijkstra(int u0)
{
    int i,j,k;
    for (i=0;i<n;i++)
    {
        dist[i]=edge[u0][i];
        s[i]=0;
        if (i!=u0 && dist[i] < INF)
            path[i]=u0;
        else
            path[i]=-1;
    }
    s[u0]=1;
    dist[u0]=0;
    for(i=0;i<n-1;i++)
    {
        int min=INF,u=u0;
        for (j=0;j<n;j++)
        {
            if (!s[j] && dist[j]<min)
            {
                u=j;min=dist[j];
            }
        }
        s[u]=1;
        for (k=0;k<n;k++)
        {
            if (!s[k] && edge[u][k] < INF && dist[u]+edge[u][k]){
                dist[k]=dist[u]+edge[u][k]; path[k]=u;
            }
        }
    }
}

int main()
{
    freopen("dijkstra.txt","r",stdin);
    int u,v,w;
    int t;
    scanf("%d",&t);
    while (t--)
    {
    scanf("%d",&n);
    while (1)
    {
        scanf("%d%d%d",&u,&v,&w);
        if (u==-1 && v==-1 && w==-1)
        {
            break;
        }
        edge[u][v]=w;
    }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (i==j)   edge[i][j]=0;
            else if (edge[i][j]==0) edge[i][j]=INF;
        }
    }
    dijkstra(0);
    int shortest[MAXN];
    for (int i=1;i<n;i++)
    {
        printf("%d\t",dist[i]);
        memset(shortest,0,sizeof(shortest));
        int k=0;
        shortest[k]=i;
        while (path[shortest[k]]!=0)
        {
            k++;shortest[k]=path[shortest[k-1]];

        }
        k++;
        shortest[k]=0;
        for (int j=k;j>0;j--)
            printf("%d->",shortest[j]);
        printf("%d\n",shortest[0]);
    }
    printf("\n");
    }
    return 0;
}
